#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
//class Solution {
//public:
//    int m, n;
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    int path1 = 0;
//    int path2 = 0;
//    vector<vector<bool>> visit;
//    vector<vector<int>> ret;
//    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
//        m = heights.size();
//        n = heights[0].size();
//        visit.resize(m);
//        for (int i = 0; i < m; i++)
//        {
//            visit[i].resize(n, true);
//        }
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                path1 = 0;
//                path2 = 0;
//                dfs(heights, i, j);
//                if (path1 > 0 && path2 > 0)
//                    ret.push_back({ i,j });
//            }
//        }
//        return ret;
//    }
//    void dfs(vector<vector<int>>& heights, int i, int j)
//    {
//        if (path1 > 0 && path2 > 0)
//            return;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if (x < 0 || y < 0)
//            {
//                path1++;
//                continue;
//            }
//            if (x >= m || y >= n)
//            {
//                path2++;
//                continue;
//            }
//            if (heights[i][j] >= heights[x][y] && visit[x][y])
//            {
//                visit[i][j] = false;
//                dfs(heights, x, y);
//                visit[i][j] = true;
//            }
//        }
//    }
//};
class Solution {
public:
    int m, n;
    int dx[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
    int dy[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        if (board[click[0]][click[1]] == 'M')
        {
            board[click[0]][click[1]] = 'X';
            return board;
        }
        m = board.size();
        n = board[0].size();


        //visit.resize(m);
        //for(int i = 0; i < m; i++)
        //{
            //visit[i].resize(n,true);
        //}
        //for(int i = 0;i< m;i++)
        //{
            //for(int j = 0; j<n;j++)
            //{
                //if(board[i][j]>='1'&&board[i][j]<='8')
                    //visit[i][j] = false;
                //if(board[i][j]=='M')
                //{
                    //visit[i][j]=false;
                //}
            //}
        //}
        dfs(board, click[0], click[1]);
        return board;
    }
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        int count = 0;
        for (int k = -1; k <= 1; k++)
        {
            for (int l = -1; l <= 1; l++)
            {
                if (i + k >= 0 && i + k < m && j + l >= 0 && j + l < n && board[i + k][j + l] == 'M')
                    count++;
            }
        }
        if (count)
        {
            board[i][j] = count + '0';
            //visit[i][j] = false;
            return;
        }
        else
        {
            board[i][j] = 'B';
            for (int k = 0; k < 8; k++)
            {
                int x = i + dx[k], y = dy[k] + j;
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
                {
                    //visit[i][j] = false;
                    dfs(board, x, y);
                    //visit[i][j] = true;
                }
            }

        }

    }
};
int main()
{
    Solution s;
    vector<vector<char>> board  = { {'E','E','E','E','E'},{'E','E','M','E','E'}, {'E','E','E','E','E'}, {'E','E','E','E','E'} };
    vector<int> click = { 3,0};
    s.updateBoard(board,click);
    //vector<vector<int>> heights{ {1,2,2,3,5} ,{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4} };
    //s.pacificAtlantic(heights);
    return 0;
}
//class Solution {
//public:
//    int m, n;
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0 };
//    void solve(vector<vector<char>>& board) {
//        m = board.size();
//        n = board[0].size();
//        for (int i = 1; i < m - 1; i++)
//        {
//            for (int j = 1; j < n - 1; j++)
//            {
//                if (board[i][j] == 'O')
//                {
//                    board[i][j] = 'I';
//                    dfs(board, i, j, 'O', 'I');
//                }
//            }
//        }
//
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (board[i][j] == 'O')
//                {
//                    dfs(board, i, j, 'I', 'O');
//                }
//            }
//        }
//        for (int i = 1; i < m - 1; i++)
//        {
//            for (int j = 1; j < n - 1; j++)
//            {
//                if (board[i][j] == 'I')
//                {
//                    board[i][j] = 'X';
//                }
//            }
//        }
//        return;
//    }
//    void dfs(vector<vector<char>>& board, int i, int j, char target, char change)
//    {
//        for (int k = 0; k < 4; k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if (x >= 1 && x < m - 1 && y >= 1 && y < n - 1 && board[x][y] == target)
//            {
//                board[x][y] = change;
//                dfs(board, x, y, target, change);
//            }
//        }
//    }
//};

class Solution {
public:
    int m, n;
    int ret;
    vector<vector<bool>> visit;
    int wardrobeFinishing(int _m, int _n, int cnt) {
        ret = 0;
        m = _m;
        n = _n;
        visit.resize(m);
        for (int i = 0; i < m; i++)
        {
            visit[i].resize(n, true);
        }
        visit[0][0] = false;
        dfs(0, 0, cnt);
        return ret;
    }
    int digit(int n)
    {
        int ret = 0;
        while (n)
        {
            ret += (n % 10);
            n /= 10;
        }
        return ret;
    }
    void dfs(int i, int j, int cnt)
    {
        if (digit(i) + digit(j) > cnt)
        {
            return;
        }
        ret++;
        if (i + 1 >= 0 && i + 1 < m && j >= 0 && j < n && visit[i + 1][j])
        {
            visit[i + 1][j] = false;
            dfs(i + 1, j, cnt);
        }
        if (i >= 0 && i < m && j + 1 >= 0 && j + 1 < n && visit[i][j + 1])
        {
            visit[i][j + 1] = false;
            dfs(i, j + 1, cnt);
        }
    }
};